package com.ssh;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.junit.Test;

public class SolveSudoku_37 {
	
	@Test
	public void test() {
		char[][] board = {  {'5','3','.','.','7','.','.','.','.'},
							{'6','.','.','1','9','5','.','.','.'},
							{'.','9','8','.','.','.','.','6','.'},
							{'8','.','.','.','6','.','.','.','3'},
							{'4','.','.','8','.','3','.','.','1'},
							{'7','.','.','.','2','.','.','.','6'},
							{'.','6','.','.','.','.','2','8','.'},
							{'.','.','.','4','1','9','.','.','5'},
							{'.','.','.','.','8','.','.','7','9'}
						};
		solveSudoku(board);
	}
	
	public void solveSudoku(char[][] board) {
		k:
        for (int i = 0; i < 9; i++) {
        	for (int j = 0; j < 9; j++) {
        		if (board[i][j] == '.') {
        			backDateSudoku(board, i, j);
        			break k;
        		}
        	}
        }
		for (int i = 0; i < 9; i++) {
			System.out.println(Arrays.toString(board[i]));
        }
		
    }
	private int backDateSudoku(char[][] board, int x, int y){
		if (isOk(board)) {
			return 0;
		}
		
		List<Character> useNum = useNum(board, x, y);
		//System.out.println("--"+useNum.toString());
		if (useNum == null || useNum.isEmpty()) {
			return 1;
		}
		int r = 0,rt = 0;
		for (int k = 0, len = useNum.size(); k < len; k++) {
			board[x][y] = useNum.get(k);
			
			/*for (int i = 0; i < 9; i++) {
				System.out.println(Arrays.toString(board[i]));
	        }*/
			
			int x1 = 0,y1 = 0;
			k:
			for (int i = 0; i < 9; i++) {
	        	for (int j = 0; j < 9; j++) {
	        		if (board[i][j] == '.') {
	        			x1 = i;
	        			y1 = j;
	        			break k;
	        		}
	        	}
	        }
			rt = backDateSudoku(board, x1, y1);
			r += rt;
			if (rt == 0) {
				return 0;
			}
			if (r == len) {
				board[x][y] = '.';
			}
		}
		return 1;
	}

	private boolean isOk(char[][] board) {
		for (int i = 0; i < 9; i++) {
        	for (int j = 0; j < 9; j++) {
        		if (board[i][j] == '.') {
        			return false;
        		}
        	}
        }
		return true;
	}
	
	
	private List<Character> useNum(char[][] board, int x, int y){
		Set<Character> haveNum = new HashSet<>();
		for (int i = 0; i < 9; i++) {
			if (board[x][i] != '.') {
				haveNum.add(board[x][i]);
			}
			if (board[i][y] != '.') {
				haveNum.add(board[i][y]);
			}
		}
		int x1 = location(x);
		int y1 = location(y);
 		for (int i = x1; i < x1+3; i++) {
 			for (int j = y1; j < y1+3; j++) {
 				if (board[i][j] != '.') {
 					haveNum.add(board[i][j]);
 				}
 	 		}
 		}
 		//System.out.println("=="+haveNum.toString());
 		List<Character> useNum = new ArrayList<>();
 		for (char i = '1'; i <= '9'; i++) {
 			if(!haveNum.contains(i)) {
 				useNum.add(i);
 			}
 		}
 		
 		return useNum;
	}
	
	
	private int location(int t) {
		if (t < 3) {
			t = 0;
		} else if (t < 6) {
			t = 3;
		} else {
			t = 6;
		}
		return t;
	}
}
